The flow of information in a network is often called xe2x80x9ctraffic,xe2x80x9d while units of information used in network communication are called xe2x80x9cpackets.xe2x80x9d Packets generally arrive at various points in the network at random intervals, resulting in xe2x80x9cburstsxe2x80x9d of traffic that may result in congestion. When congestion occurs, the network""s ability to deliver the packets to their destinations is taxed, sometimes causing one or more packets to be lost or delayed. To relieve congestion, various traffic shaping techniques have been developed. One traffic shaping technique, for example, enforces an average traffic flow rate that smoothes out bursts. Another more widely-used traffic shaping technique, called xe2x80x9cthe token bucket model,xe2x80x9d accommodates some bursts of traffic for short periods of time.
Measurements of the average rate of traffic flow and the xe2x80x9cburstinessxe2x80x9d of the traffic are useful in these contexts. Measurements of rate and burstiness can be computed by computer according to a variety of algorithms. Many conventional algorithms are of complexity O(n log n), in which n is the number of packets in the traffic pattern, meaning that execution time is proportional to the number of packets times the log of the number of packets.